package com.ShangGuiGu.recursion;

/**
 * @auther zsj
 * @Date 2022/1/13
 * <p>
 * 迷宫回溯问题
 **/
public class MiGong {
    public static void main(String[] args) {
        //迷宫肯定是一个二维数组来模拟的
        int[][] map = new int[8][7];
        //1 墙
        for (int i = 0; i < map.length - 1; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        //看一下
        for (int i = 0; i < map.length; i++) {
            for (int i1 = 0; i1 < map.length - 1; i1++) {
                 System.out.print(map[i][i1]);
            }
            System.out.println();
        }

        setWay(map,1,1);


        System.out.println("=========================");
        for (int i = 0; i < map.length; i++) {
            for (int i1 = 0; i1 < map.length - 1; i1++) {
                System.out.print(map[i][i1]);
            }
            System.out.println();
        }

    }


    /**
     * the param i  and param j is you begin location
     *
     * @param map you must have a base map to initialization
     * @param i   location line
     * @param j   location column
     * @return find the way is true else false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            //说明路找到了
            return true;
        } else {
            if (map[i][j] == 0) {
                //策略  下 右 上  左
                //说明当前点是没有走过的
                map[i][j] = 2;//假定该点是可以走通的
                if (setWay(map, i + 1, j)) {
                    //向下走
                    return true;
                } else if (setWay(map, i, j + 1)) {
                    //向右走
                    return true;
                } else if (setWay(map, i - 1, j)) {
                    //向上走
                    return true;
                } else if (setWay(map, i, j - 1)) {
                    //向左走
                    return true;
                } else {
                    //往哪里都走不通
                    map[i][j] = 3;
                    return false;
                }
            } else {
                return false;
            }

        }

    }
}
